西北师范大学普通专升本招生
《计算机科学与技术专业》专业综合课考试大纲
一、考试目的
西北师范大学专升本招生《计算机科学与技术专业》专业综合课包括两部分内容：数据结构和操作系统。考试目的是检查学生是否牢固掌握《数据结构》和《操作系统》两门课程相关知识的一次水平测定，全面考核普通高校计算机专科（含高职）应届毕业生对专业核心课程《数据结构》和《操作系统》的掌握程度，要求学生比较系统地理解数据结构和操作系统的基本概念和基本理论。
二、考试内容
数据结构部分：
（一）数据结构的概念
1. 什么是数据结构（逻辑结构，存储结构，运算）；
2. 算法，算法分析，算法特性；
3.算法与程序的差别。
（二）顺序表
1.线性表（向量）的定义，操作，算法；
2.栈的定义，操作，算法；
3.队列的定义，操作，算法。
（三）链表
1.链表的概念及其特点；
2.单链表的概念，存储表示，查找，输入，删除等运算和算法；
3.双链表的概念，存储表示，查找，输入，删除等运算和算法。
（四）排序
1.排序的概念，内排序和外排序，排序算法的稳定性；
2.内排序的分类；
3.各种排序的基本思想，例子，算法，稳定性，时空复杂度。
（五）线性表的检索
1.顺序检索的概念，算法，时间复杂度；
2.二分检索的概念，算法，时间复杂度；
3.散列法：（1）基本概念；
（2）散列函数的构造方法；
（3）冲突的处理：拉链法，开地址法，算法。
（六）树形结构
1.树和二叉树的概念；
2.树（林）与二叉树的相互转换；
3.二叉树的存储表示（1）二叉链表（2）完全二叉树的顺序存储；
4.二叉树与树的周游（遍历）的概念，各种周游方法；
5.二叉树遍历的算法；
6.二叉树中其他算法（结点统计，高度计算，左右子树交换等）。
（七）树表检索
1.二叉排序树的概念，插入，删除运算；
2.最佳二叉排序树的概念，建立方法，算法；
3.平衡二叉排序树（AVL）的概念，构造方法（如何调整。）
（八）图
1.图的概念和相关术语；
2.图的存储表示方法：邻接矩阵，邻接表，邻接多重表；
3.图的遍历：深度优先遍历，广度优先遍历；
4.最小生成树的概念，构造方法，算法；
5.拓扑排序的概念，算法思想，算法；
6.最短路径的概念，构造方法，算法。
操作系统部分：
（一）操作系统的基本概念
1. 理解操作系统的定义、特征就及设置操作系统的目的；
2. 了解操作系统在计算机系统中的地位、操作系统的形成和发展；
3. 掌握多道程序设计和虚拟处理机的基本原理；
4. 了解操作系统的分类；掌握分时系统的特征。
5. 了解研究操作系统的几种不同观点。
（二）用户与操作系统的接口
1. 理解作业，作业步，作业流的概念；
2. 掌握脱机作业控制方式，联机作业控制方式；
3. 了解系统功能调用。
（三）作业管理
1. 理解并掌握作业管理的基本功能；
2. 理解并掌握作业控制的两种方式；
3.掌握批处理作业的几种调度算法以及作业调度和进程调度的关系；
4. 掌握脱机输入输出和SPOOLING 技术；
5. 了解作业控制块和作业后备队列。
（四）进程管理
1. 理解并掌握程序的并发执行和资源共享；
2. 掌握程序并发执行的特性；
3. 理解并掌握进程的概念、进程的表示和调度状态；
4. 了解进程的控制机构及进程控制原语；
5. 熟练掌握常用的进程调度算法（静态优先级法，动态优先级法，时间片轮转法）；
6. 熟练掌握作业，进程，和程序之间的区别和联系；
7. 理解并掌握进程间的同步与互斥；
8. 理解信号量及P，V操作，并能利用信号量机制实现进程间的同步与互斥；
9. 理解并熟练掌握利用信号量机制实现的生产者——消费者问题；
10.了解高级通讯原语（消息缓冲方式，信箱方式）；
11. 理解并掌握死锁的概念、起因及产生死锁的必要条件；
12. 了解处理死锁的四种对策（预防策略，避免策略，检测和解除）；
13．了解单项资源的银行家算法和多种资源的银行家算法；
